import re

class TrieNode:
    def __init__(self, char=''):
        self.char = char      # 节点字符
        self.children = {}    # 子节点字典
        self.is_end = False   # 是否单词结尾

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode(char)
            node = node.children[char]
        node.is_end = True

def generate_minimized_regex(words):
    if not words:
        return ""
    
    # 构建 Trie
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    # 递归生成正则（非根节点）
    def _traverse(node):
        current_char = re.escape(node.char)  # 转义特殊字符
        
        # 叶子节点：直接返回字符
        if not node.children:
            return current_char
        
        # 递归子节点
        child_regexes = []
        for child in node.children.values():
            child_regexes.append(_traverse(child))
        
        # 合并子节点的正则
        if len(child_regexes) == 1:
            sub_regex = child_regexes[0]
        else:
            sub_regex = f"(?:{'|'.join(child_regexes)})"
        
        # 当前节点是单词结尾：子部分可选
        if node.is_end:
            # 优化：子正则为单字符时直接加 ?（如 'b?'）
            if len(sub_regex) == 1 or (sub_regex.startswith('\\') and len(sub_regex) == 2):
                return f"{current_char}{sub_regex}?"
            else:
                return f"{current_char}(?:{sub_regex})?"
        else:
            return f"{current_char}{sub_regex}"
    
    # 处理根节点的子节点
    child_regexes = []
    for child in trie.root.children.values():
        child_regexes.append(_traverse(child))
    
    # 合并单字符正则（如 ['e','f'] → '[ef]'）
    single_chars = []
    other_regexes = []
    for regex in child_regexes:
        if len(regex) == 1 or (regex.startswith('\\') and len(regex) == 2):
            single_chars.append(regex)
        else:
            other_regexes.append(regex)
    
    if single_chars:
        # 去重并排序（可选）
        single_chars = sorted(set(single_chars))
        char_class = f"[{''.join(single_chars)}]" if len(single_chars) > 1 else single_chars[0]
        other_regexes.append(char_class)
    
    # 用 | 连接所有部分
    return "|".join(other_regexes)

# 测试
words = ['a', 'ab', 'bc', 'f', 'e']
regex = generate_minimized_regex(words)
print(regex)  # 输出：ab?|bc|[ef]